package leetcode.editor.cn.q1_300.q200;
//你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 
//
// 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表
//示如果要学习课程 ai 则 必须 先学习课程 bi 。 
//
// 
// 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 
// 
//
// 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：true
//解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。 
//
// 示例 2： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
//输出：false
//解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。 
//
// 
//
// 提示： 
//
// 
// 1 <= numCourses <= 10⁵ 
// 0 <= prerequisites.length <= 5000 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// prerequisites[i] 中的所有课程对 互不相同

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 一个课程的前提有可能是多个课程，也有可能是多个课程的前提是同一个课程，这是一个图结构
 */
public class Q207_CourseSchedule {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            if (prerequisites == null || prerequisites.length == 0) return true;
            // 保存所有的 index 对应的前提
            List<List<Integer>> preList = new ArrayList<>();
            // 保存所有的 index 对应的后续
            List<List<Integer>> nextList = new ArrayList<>();
            for (int i = 0; i < numCourses; i++) {
                preList.add(new ArrayList<>());
                nextList.add(new ArrayList<>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                int next = prerequisites[i][0];
                int pre = prerequisites[i][1];

                preList.get(next).add(pre);
                nextList.get(pre).add(next);
            }
            List<Integer> noPreList = new ArrayList<>();
            // 获取到可以直接学习的课程
            for (int i = 0; i < preList.size(); i++) {
                if (preList.get(i).size() == 0) noPreList.add(i);
            }

            Set<Integer> learned = new HashSet<>();
            learned.addAll(noPreList);
            for (Integer i : noPreList) {
                if (learn(preList, nextList, i, learned, numCourses)) return true;
            }

            return false;
        }

        private boolean learn(List<List<Integer>> preList, List<List<Integer>> nextList, int pre, Set learned, int size) {
            if (size == learned.size()) return true;

            for (Integer next : nextList.get(pre)) {
                if (learned.containsAll(preList.get(next))) {
                    learned.add(next);
                    if (learn(preList, nextList, next, learned, size)) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q207_CourseSchedule().new Solution();
        // TO TEST
        int[][] arr = new int[][]{{1, 0}, {2, 6}, {1, 7}, {6, 4}, {7, 0}, {0, 5}};
        System.out.println(solution.canFinish(8, arr));
        arr = new int[][]{{0, 1}, {1, 0}};
        System.out.println(solution.canFinish(2, arr));
        arr = new int[][]{{0, 2}, {1, 2}, {2, 0}};
        System.out.println(solution.canFinish(3, arr));
        arr = new int[][]{{1, 4}, {2, 4}, {3, 1}, {3, 2}};
        System.out.println(solution.canFinish(5, arr));
        arr = new int[][]{{0, 1}};
        System.out.println(solution.canFinish(2, arr));
        arr = new int[][]{{0, 1}, {1, 2}, {2, 0}};
        System.out.println(solution.canFinish(3, arr));
        arr = new int[][]{{0, 1}, {1, 2}, {0, 2}};
        System.out.println(solution.canFinish(3, arr));
    }
}